import java.util.ArrayList;
import java.util.List;

public class Solution68 {
    private void appendBlank(StringBuilder tmpRes, int maxWidth){
        while(tmpRes.length() < maxWidth){
            tmpRes.append(' ');
        }
    }

    private void appendBlankWithNum(StringBuilder tmpRes, int num){
        for (int i = 0; i < num; i++) {
            tmpRes.append(' ');
        }
    }

    private int[] getProbBlankNumArr(int leftWidth, int len){
        if(len == 0){
            return null;
        }
        int blankNum = leftWidth/len;
        int[] blankNumArr = new int[len];
        for (int i = 0; i < len; i++) {
            blankNumArr[i] = blankNum;
        }
        for (int i = 0; i < leftWidth%len; i++) {
            blankNumArr[i]++;
        }
        return blankNumArr;
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int ind = 0;
        while(ind < words.length){
            StringBuilder tmpRes = new StringBuilder();
            int leftWidth = maxWidth;
            int startInd = ind;
            while(ind<words.length && leftWidth - words[ind].length()>=(ind-startInd)){
                leftWidth -= words[ind].length();
                ind++;
            }
            int len = ind - startInd;
            if(ind == words.length){
                for (int i = startInd; i < ind; i++) {
                    tmpRes.append(words[i]);
                    if(i != ind-1) {
                        tmpRes.append(' ');
                    }
                }
                appendBlank(tmpRes, maxWidth);
            }
            else{
                int[] blankNumArr = getProbBlankNumArr(leftWidth, len-1);
                for (int i = startInd; i < ind; i++) {
                    tmpRes.append(words[i]);
                    if(i != ind-1) {
                        appendBlankWithNum(tmpRes, blankNumArr[i-startInd]);
                    }
                }
                appendBlank(tmpRes, maxWidth);
            }
            res.add(tmpRes.toString());
        }
        return res;
    }

    public static void main(String[] args) {
        Solution68 s = new Solution68();
        System.out.println(s.fullJustify(new String[]{"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"},
        20));
    }
}
